#include <iostream>

using namespace std;

struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(): val(0), next(nullptr) {};
    LinkedNode(int x): val(x), next(nullptr) {};
};

// 解题关键：画草图，终止条件搞清楚就很简单清晰了
// 双指针迭代
LinkedNode* reverseList(LinkedNode* head) {
    LinkedNode* prev = nullptr;
    LinkedNode* current = head;
    while (current != nullptr) {
        LinkedNode* temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }

    return prev;
}

LinkedNode* reverse(LinkedNode* pre, LinkedNode* current) {
    if (current == nullptr) {
        return pre;
    }
    LinkedNode* temp = current->next;
    current->next = pre;
    pre = current;
    current = temp;
    return reverse(pre, current);
}

// 递归
LinkedNode* reverseList2(LinkedNode* head) {
    return reverse(nullptr, head);
}

void printListNode(LinkedNode* head) {
    LinkedNode* current = head;
    while (current != nullptr) {
        cout << current->val << " ";
        current = current->next;
    }
    cout << endl;
}

int main() {
    LinkedNode* node1 = new LinkedNode(1);
    LinkedNode* node2 = new LinkedNode(2);
    LinkedNode* node3 = new LinkedNode(6);
    LinkedNode* node4 = new LinkedNode(3);
    LinkedNode* node5 = new LinkedNode(4);
    LinkedNode* node6 = new LinkedNode(5);
    LinkedNode* node7 = new LinkedNode(6);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    node6->next = node7;

    cout << "origin: " << "\n";
    printListNode(node1);

    node1 = reverseList2(node1);

    cout << "after: " << "\n";
    printListNode(node1);

    return 0;
}